﻿#pragma once
#include <iostream>
#include <vector>
using namespace std;
typedef enum { RB_RED,RB_BLACK} RBColor;

#define stature(x) (x->_bf) ? -1 : x->_bf

// 节点定义
template<typename T>
struct BinNode
{
	typedef BinNode<T> BinNode;
	T _data;
	BinNode* _parent;		// 三叉结构
	BinNode* _leftch;
	BinNode* _rightch;
	int _height;
	int _bf;	// 平衡因子
	RBColor _col;
	
	BinNode() = default;
	BinNode(const T& data):_data(data),_parent(nullptr),
			_leftch(nullptr),_rightch(nullptr),_bf(0),_col(RB_RED){}

	BinNode(const T& data,const T& parent) :_data(data), _parent(parent),
		_leftch(nullptr), _rightch(nullptr), _bf(0), _col(RB_RED) {}

	// 比较器
	bool operator<(BinNode const& bn) { return _data < bn._data; }
	bool operator==(BinNode const& bn) { return _data == bn._data; }


	// 本质就是求该节点的左右高度
	int size();
	// 真正进行插入的操作
	BinNode insertAsLeftch(const T&);
	BinNode insertAsRightch(const T&);
};

// 本质就是求该节点的左右高度
template<typename T>
int BinNode<T>::size() { return _bf; }
// 真正进行插入的操作
template<typename T>
BinNode<T> BinNode<T>::insertAsLeftch(const T&) { return _leftch = new BinNode(T); }
template<typename T>
BinNode<T> BinNode<T>::insertAsRightch(const T&) { return _rightch = new BinNode(T); }

template<typename T>
class BinaryTree
{
	typedef BinNode<T> BinNode;
protected:
	int _size;	// 树图规模
	BinNode* _root;
	inline int _updateheight(BinNode* x)
	{
		if (x == nullptr) return 0;
		return 1 + max(_updateheight(x->_leftch),_updateheight(x->_rightch);
	}

	// 当前节点高度
	virtual int updateHeight(BinNode* x)
	{
		return x->_bf = _updateheight(x);
	}

	void updateHeightAbove(BinNode* x)
	{
		// 从x开始向上更新
		while (x) {
				
			x = x->_parent;
		}
	}

public:
	BinaryTree():_size(0),_root(nullptr){}
	~BinaryTree() { if (_root) remove(_root); }
	
	int size() const { return _size; }
	bool empty() const { return !_root; }
	BinNode root() const { return _root; }

	// Node was Inserted
	BinNode* insertAsRoot(T const& e);
	BinNode* insertAsLC(BinNode* x, T const& e);
	BinNode* insertAsRC(BinNode* x, T const& e);
};

template<typename T>
BinNode<T>* BinaryTree<T>::insertAsRoot(T const& e)
{
	// 作为根节点插入
	_size = 1;
	return _root = new BinNode<T>(e);
}

template<typename T>
BinNode<T>* BinaryTree<T>::insertAsLC(BinNode* x, T const& e)
{
	_size++;
	x->insertAsLeftch(e);
	updateHeight(x);
	return x->_leftch;
}

template<typename T>
BinNode<T>* BinaryTree<T>::insertAsRC(BinNode* x, T const& e)
{
	_size++;
	x->insertAsRightch(e);
	updateHeight(x);
	return x->_rightch;
}

template<typename K, typename V>
struct Entry
{
	typedef Entry<K, V> Self;
	K _k;
	V _v;
	Entry(const K& key, const V& val) :_k(key), _v(val) {}

	bool operator==(const Self& e) { return _k == e._k; }
	bool operator>(const Self& e) { return _k > e._k; }
	bool operator<(const Self& e) { return _k < e._k; }
	bool operator!=(const Self& e) { return _k < e._k; }
};

namespace BST
{
	// 提供搜索、插入、删除
	template<typename T>
	class BST : public BinaryTree<T>
	{
		typedef BinNode<T> BinNode;
	protected:
		BinNode* _hot;		// 倒数第二层的 —— 非叶子节点
	public:
		// 强制子类 根据树的特性重写 三个接口
		virtual BinNode* search(const T& e);
		virtual BinNode* insert(const T& e);
		virtual bool remove(const T& e);

		static BinNode* searchIn(BinNode* v, const T& e, BinNode*& hot)
		{
			// find the node
			if (v != nullptr && (e == v->_data)) return v;
			hot = v;
			return searchIn((v->_data > e ? v->_leftch : v->_rightch), e, hot);
		}

		bool HasLChild(BinNode* x) { return x->_leftch; }
		bool HasRChild(BinNode* x) { return x->_rightch; }
		BinNode succ()
		{
			// Find the node in minright
			BinNode* cur = _root;
			while (cur->_rightch) {
				cur = cur->_rightch;	
				while (HasLChild(cur)) cur = cur->_leftch;
			}
			else {
				// otherwise find node from left
				cur = cur->_leftch;
				while (HasRChild(cur)) cur = cur->_rightch;
			}
			return cur;
		}

		static BinNode* removeAt(BinNode*& x, BinNode*& hot)
		{
			// p 为要删除 节点
			BinNode* w = x;
			BinNode* succ = nullptr; // 继承点
			if (!HasLChild(x)) // 左子树为空
				succ = x = x->_rightch;
			else if (!HasRChild(x))
				succ = x = x->_leftch;
			else
			{
				// 两个节点
				w = w->succ();
				swap(p->_data, x->_data);
				// 前后连接
				BinNode* u = w->_parent;
				((u == x) ? u->_rightch : u->_leftch) = succ = w->_rightch;
			}

			hot = w->_parent;
			if (succ) succ->parent = hot;
			delete(w->_data);
			delete(w);	
			return succ;
		}
	};

	// 查找算法及其实现
	template<typename T>
	BinNode<T>* BST<T>::search(const T& e) { return searchIn(_root, e, _hot = NULL); }

	template<typename T>
	BinNode<T>* BST<T>::insert(const T& e)
	{
		BinNode* x = search(e);
		if (x) return x;
		// 因为引用的缘故,hot指向的就是 x要插入的父节点
		x = new BinNode<T>(e,_hot);
		_size++;
		updateHeightAbove(x);
		return x;
	}

	template<typename T>
	bool BST<T>::remove(const T& e)
	{
		BinNode x = search(e);
		if (!x) return false;
		removeAt(x, _hot);
		_size--;
		updateHeightAbove(x);
		return true;
	}
}

namespace AVLTree
{
	template<typename T>
	class AVLTree :public BST::BST<T> 
	{
		typedef BinNode<T> BinNode;
	public:
		// 插入、删除
		BinNode* Insert(const T&);
		bool Remove(const T&);
		void rotateAt(BinNode*);
		// Search可以复用BST
		// BinNode*  BST::BST<T>::search(const T& e);
	private:
		int getHeight(BinNode* root)
		{
			return root == nullptr ? 0 : 1 + max(getHeight(root->_leftch), getHeight(root->_rightch));
		}

		// 判断是否平衡
		inline bool Balanced(BinNode* root)
		{
			if (root->_leftch == nullptr && root->_rightch == nullptr) return true;
			int leftHeight = getHeight(root->_leftch);
			int rightHeight = getHeight(root->_rightch);

			return (leftHeight == rightHeight) &&
				    Balanced(root->_leftch &&
					Balanced(root->_rightch);
		}
		inline int BalFac(BinNode* root){ return getHeight(root->_leftch) - getHeight(root->_rightch); }
		inline bool AvlBalanced(BinNode* root) { return (-2 < BalFac(x)) && (2 > BalFac(x)); }
	};

	template<class T>
	BinNode<T>* AVLTree<T>::Insert(const T& e)
	{
		// 确讣目标节点不存在
		BinNode* x = search(x); 
		if (x) return x;
		x = new BinNode<T>(e,_hot);
		_size++;
		// 节点更新
		for (BinNode* g = _hot; g; g = g->parent)
		{
			if (!AvlBalanced(g)) {
				// 失衡
				 // 传递失衡的节点
				rotateAt(tallerChild(g));
				break;
			}
			else updateHeight(g);
		}

		return x;
	}

	template<class T>
	bool AVLTree<T>::Remove(const T& e)
	{
		BinNode<T>* x = search(e); if (!x) return false;
		removeAt(x, _hot); _size--;

		for (BinNode<T*> g = _hot; g; g = g->parent) {
			if (!AvlBalanced(g))
				rotateAt(tallerChild(g));
			updateHeight(g);
		}
		return true;
	}

// 在左、右孩子中叏更高者，若等高，则不父亲p同侧者优先
#define tallerChild(x)  ( \
	stature((x)->lChild) > stature((x)->rChild) ? (x)->lChild :  ( \
	stature((x)->rChild) > stature((x)->lChild) ? (x)->rChild : ( \
	IsLChild(*(x)) ? (x)->lChild : (x)->rChild )\
		)\
	)

	template<class T>
	void AVLTree<T>::rotateAt(BinNode* v)
	{
		BinNode* p = v->_parent, * g = p->_parent;
		// 监测平衡因子
		if ((g->_leftch == p && p->_leftch == v) || (g->_leftch == p && p->_leftch == v))
		{
			// 左边高 右旋 
			rotateL(g);
			v->_bf = p->_bf = g->_bf = 0;
		}
		else if ((g->_rightch == p && p->_rightch == v) || (g->_rightch == p && p->_rightch == v))
		{
			rotateR(g);
			v->_bf = p->_bf = g->_bf = 0;
		}
		else
		{
			if (g->_leftch == p && p->_rightch == v)
			{
				// 左右双旋
				rotateL(p);
				rotateR(g);

				if (v->_bf == -1)
				{
					v->_bf = p->_bf = 0;
					g->_bf = 1;
				}
				else if (v->_bf == 1)
				{
					v->_bf = g->_bf = 0;
					p->_bf = -1;
				}
				else v->_bf = p->_bf = g->_bf = 0;
			}
			else
			{
				rotateR(p);
				rotateL(g);
				if (v->_bf == -1)
				{
					v->_bf = g->_bf = 0;
					p->_bf = 1;
				}
				else if (v->_bf == 1)
				{
					v->_bf = g->_bf = 0;
					g->_bf = -1;
				}
				else v->_bf = p->_bf = g->_bf = 0;
			}
		}
	}
}

namespace RBTree
{
	template <typename T> class RedBlack : public BST::BST<T>
	{
		typedef BinNode<T> BinNode;
	private:
		inline bool isBlack(BinNode* node) { return (!(node) || (RB_BLACK == (node)->color)); }
		inline bool IsRed(BinNode* node) { return !isBlack(node); }
		inline void  BlackHeightUpdated(BinNode* node)
		{
			// 左右高度 是否相等 && 检测 
			return stature(node->_leftch) == stature(node->_rightch) &&
				stature(node->_height) == (IsRed(node) ? stature(node->_leftch) : stature(node->_leftch + 1));
		}

		inline int updateHeight(BinNode* x)
		{
			// 获取左右高度
			x->height = max(stature(x->lChild), stature(x->rChild));
			// 若弼前节点为黑，则计入黑深度
			return IsBlack(x) ? x->height++ : x->height;
		}
	public:

		// 返回uncle
		inline BinNode* uncle(BinNode* x) { return x->_parent->_leftch == x ? x->_parent->_rightch : x->_parent->_leftch; }
		void solveDoubleRed(BinNode* x)
		{
			// 如果已经迭代到了根节点 直接结束即可 并置黑
			if (IsRoot(*x))
			{
				x->_col = RB_BLACK;
				x->height++;
				return;
			}

			//若p为黑，则可终止调整 因为新增节点为红
			BinNode* p = x->_parent; if (isBlack(p)) return;
			// 既然p为红，则x的祖父必存在，且必为黑色
			BinNode* g = p->_parent;
			BinNode* u = uncle(x);

			// uncle存在且为黑 或 uncle不存在
			if (IsBlack(u) || !u) {
				g->color = RB_RED; //g必定由黑转红
				// 同侧单旋
				if (IsLChild(x) == IsLChild(p))
					p->_col = RB_RED;
				else if (IsRChild(x) == IsRChild(x))
					p->_col = RB_RED;
				else x->_col = RB_BLACK; // 折线

				BinNode* pp = g->_parent;
				BinNode* r = rotateAt(x);
				r->parent = gg; //与曾祖父联接
			}
			else {
				// 存在且为红
				p->_col = RB_BLACK;
				p->height++; //p由红转黑
				g->_col = RB_BLACK;
				u->height++; //u由红转黑

				if (!IsRoot(*g)) g->color = RB_RED; //g若非根，则转红
				solveDoubleRed(g); // 递归调整 以g
			}
		}

		void solveDoubleBlack(BinNode* r)
		{
			// 父节点
			BinNode* parent = r ? r->parent : _hot;
			if (!p) return;
			// 兄弟
			BinNode* uncle = (r == p->lChild) ? p->rChild : p->lChild;

			if (isBlack(u))
			{
				// 兄弟为黑
				BinNode* t = nullptr;

				// 兄弟拥有红色节点
				// 优先选取左孩子
				if (HasLChild(*s) && IsRed(s->lChild)) t = s->lChild;
				else if (HasRChild(*s) && IsRed(s->rChild)) t = s->rChild;
				if (t) {
					// 以p为旋转点 uncle与t染黑 uncle旋转到根变红
					t->_col = parent->_col = RB_RED;
					uncle->_col = RB_BLACK;
					rotateAt(parent);
				}
				else {
					// 兄弟节点只有黑色节点
					// 如果父亲节点 是红色节点 直接下压染色 不会溢出
					if (IsRed(parent)) {
						// 父亲下压染黑 兄弟染红
						parent->_col = RB_BLACK;
						uncle->_col = RB_RED;
					}
					else {
						// 父节点为黑色下压而溢出 需要进行调整
						// 我们只是将父节点作为删除节点~ 并不真正删除 再次进行一次染色
						// 此时并非把parent看作 拥有 红色节点进行  —— 替换、删除
						// 而是重新进入 —— 兄弟节点是否为红\黑 
						solveDoubleBlack(parent);
						uncle->_col = RB_RED;
					}
				}
			}
			else
			{
				// 兄弟为红 
				// 我们需要进行旋转，让兄弟成为新的根 并染黑 —— 上溢
				// 父节点下压染黑完成平衡
				uncle->_col = RB_BLACK;
				parent->_col = RB_RED;
				// 进行旋转 以uncle为 主旋点
				rotateAt(uncle);
			}
		}

		BinNode* insert(const T& e);
		bool remove(const T& e);
	};

	template<typename T>
	BinNode<T>* RedBlack<T>::insert(const T& e)
	{
		BinNode<T>* x = search(e); if (x) return x;
		x = new BinNode(e, _hot);
		_size++;
		// 修正
		solveDoubleRed(x);
		return x;
	}

	template<typename T>
	bool RedBlack<T>::remove(const T& e)
	{
		BinNode<T>* x = search(e); if (!x) return false;

		// r为 _hot指向边 删除的 继承节点
		// 首先进行移除 返回的是和后继节点 —— 进行替换的点
		BinNode<T>* r = removeAt(x, _hot); if (0 >= --_size) return true;

		// 根节点的hot 为 nullptr
		if (!_hot)
			_root->color = RB_BLACK; updateHeight(_root); return true;

		// 调整高度
		if (BlackHeightUpdated(_hot)) return true;

		// 如果后继为红 删除的一定是黑色节点
		// 我们需要补齐这个空缺 把后继节点r 继续染黑处理
		// 对应 —— ① 删除节点拥有一个红色节点 
		if (IsRed(r))
		{
			r->__col = RB_BLACK;
			r->_heght++;
			return true;
		}
		// 修正双黑
		solveDoubleBlack(r);
		return true;
	}

	template<typename T>
	struct BTNode
	{
		BinNode<T>* _parent;	// 回溯节点
		vector<T*> _keys;		// 关键码
		vector<T*> _childs;		// 分支

		// 初始构造根节点，叧能作为根节点创建，而且初始时有0个关键码和1个空孩子指针
		BTNode() {
			_parent = nullptr;
			_childs.insert(0, nullptr);
		}

		BTNode(T e, BinNode<T>* lc = nullptr, BinNode<T>* rc = nullptr)
		{
			_parent = NULL; //作为根节点，而且初始化

			// 构建其内部结构: 关键码+左右子树
			_keys.insert(0, e);
			_childs.insert(0, lc);
			_childs.insert(1, rc);
			// 回指
			if (lc) lc->parent = this; if (rc) rc->parent = this;
		}
	};


	template<class T>
	class BTree
	{
		typedef BTNode<T> BTNode;
	private:
		int _size;					// 记录关键码总数
		int _order = 3;				// B-树阶次 这里默认为3

		BTNode* _root;				// 根节点
		BTNode* _hot;				// 通过BST::Search() 找到的前驱或后继节点

		int const order() { return _order; }	// 阶次
		int const size() { return _size; }		// 规模
		BTNode* root() return { _root; }		// 树根
		bool empty() const { return !_root; }

		void solveUnderflow(BTNode* v)		// 因删除而破坏平衡
		{
			// 不存在关键码下限 直接返回
			if ((_order + 1) / 2 <= v->_childs.size()) return;

			BTNode* p = v->_parent;
			if (!p) {
				// 已经递归到了根节点
				if (!v->_keys.size() && v->_childs[0]) {
					// 此时这个B树 不存在任何关键码
					_root = v->_childs[0];
					_root->_parent = nullptr;
					v->child[0] = NULL;
					// 将这个 节点删除
					release(v);
				}
				return;
			}

			// 找到连接v的指针
			size_t r = 0;
			while (p->_childs[r] != v) r++;

			// 向左兄弟借关键码
			if (0 < r)
			{
				// 因为不是第一个孩子 所以必存在左兄弟
				BTNode ls = p->child[r - 1];
				// 左兄弟是富裕的
				if ((_order + 1) / 2 < ls->_childs.size()) {
					// p借出关键码 —— 向下插入0位置
					v->_keys.insert(0, p->_keys[r - 1]);
					// 找出左兄弟的 最大节点 替代
					p->_keys[r - 1] = ls->_keys.remove(ls->key.size() - 1);

					// 将上提节点的子节点 更新给V
					v->_childs.insert(0, ls->_childs.remove(ls->_childs.size() - 1));
					// 指回父节点
					if (v->_childs[0]) v->_childs[0]->parent = v;
					return;
				}
			}


			if (p->_childs.size() - 1 > r) 
			{
				// 因为不是最后一个孩子 所以必存在右兄弟
				BTNode rs = p->child[r + 1];
				// 右兄弟是富裕的
				if ((_order + 1) / 2 < rs->_childs.size()) {
					
					// 将父节点进行下溢
					v->_keys.insert(v->_keys.size(), p->_keys[r]);
					// 将rs中的最小节点 提上替代
					p->_keys[r - 1] = ls->_keys.remove(0);
					
					// 将上提节点的子节点 更新给V
					v->_childs.insert(v->_childs.size(), rs->_childs.remove(0));
					// 指回父节点
					if (v->_childs[v->_childs.size() - 1])
						v->_childs[v->_childs.size() - 1]->_parent = v;
				}
			}


			// 左右兄弟合并
			if (0 < r) 
			{
				// 与左兄弟合并
				BTNode ls = p->_childs[r - 1];

				// 将右半子树 并入 左兄各地
				ls->_keys.insert(ls->_keys.size(), p->_keys.remove(r - 1)); 
				// 删除右半部分
				p->_childs.remove(r);
				
				// 转移新的子节点
				ls->_childs.insert(ls->_childs.size(), v->_childs.remove(0));
				if (ls->_childs[ls->_childs.size() - 1])
					ls->_childs[ls->_childs.size() - 1]->parent = ls;	// 回指新父节点
				
				// v剩余的关键码和孩子，依次转入ls
				while (!v->_keys.empty())
				{
					ls->_keys.insert(ls->_keys.size(), v->_keys.remove(0));
					ls->_childs.insert(ls->_childs.size(), v->_childs.remove(0));
					if (ls->_childs[ls->_childs.size() - 1]) ls->_childs[ls->_childs.size() - 1]->_parent = ls;
				}
				release(v);
			}
			else {
				BTNode ls = p->_childs[r + 1];

				rs->_keys.insert(0, p->_keys.remove(r));
				p->_childs.remove(r);

				rs->child.insert(0, v->child.remove(v->child.size() - 1));
				if (rs->child[0]) rs->child[0]->parent = rs;
				while (!v->key.empty())
				{
					rs->key.insert(0, v->key.remove(v->key.size() - 1));
					rs->child.insert(0, v->child.remove(v->child.size() - 1));
					if (rs->child[0]) rs->child[0]->parent = rs;
				}
				release(v);
			}

			// 向借的父节点进行递归监测
			solveUnderflow(p);
			return;
		}

		void solveOverflow(BTNode* v)		// 因插入而破坏平衡
		{
			// 未满足溢出
			if (_order >= v->child.size()) return;
			
			// 找到 中间节点
			size_t pos = _order / 2;
			BTNode* u = new BTNode();


			// 分裂v中的右侧的孩子 给u 
			for (int i = 0;i < _order - pos - 1 ;++i)
			{
				// 将右孩子从v中移除 并插入到u中
				u->_childs.insert(i, v->_childs.remove(pos + 1));
				u->_keys.insert(i, v->_keys.remove(pos + 1));
			}
			// 移动最右孩子
			u->_childs[_order - pos - 1] = v->_childs.remove(pos + 1);
			// 回指父节点
			if (u->_childs[0]) {
				for (size_t j = 0; j < _order - pos; j++) {
					u->_childs[j]->parent = u;
				}
			}

			BTNode* p = v->_parent;
			// 根节点溢出 需要创建新的
			if (!p) { _root = p = new BTNode<T>(); p->child[0] = v; v->_parent = p; }

			// 我们需要修改p中 指向u的 指针
			size_t mid = 1 + p->_keys.search(v->key[0]);
			// 上提 到右边
			p->_keys.insert(mid + 1, v->_keys.remove(pos));
			// 连接修改 分裂出去的右子树
			p->_childs.insert(mid + 1, u);

			// 节点的分裂了 但是你上体节点可能导致 父节点重新溢出
			solveOverflow(p);
		}

	public:
		BTree() : _size(0) {}
		~BTree() { if (_root) delete(_root); }

		BTNode* search(const T& e)
		{
			Node* cur = _root;
			_hot = nullptr;

			while (cur)
			{
				// 找到不大于e的关键码
				size_t pos = _root->_keys.find(e);
				if (pos >= 0 && _root->_keys[pos]) return _root->_keys[pos];
				_hot = cur;
				cur = cur->_childs[pos + 1];	// 右子树遍历
			}	
			// 不存在
			return nullptr;
		}

		// B树的插入与删除
		bool insert(const T& e)
		{
			// 我们通过search可以查找e 是否存在
			// 并更新了成员函数_hot 表面新插入节点要插入的位置
			BTNode* v = search(e);
			if (v) return false;

			// 在当前节点，找到合适的位置插入
			// pos:表示关键码不大于e的位置
			size_t pos = _hot->_keys.find(pos);
			// 将新关键码插入到对应位置
			_hot->_keys->insert(pos + 1, e);
			
			// 更新分支	该新节点没有连接任何子树
			_hot->_childs.insert(r + 2, nullptr);
			++_size;
			// 调整平衡
			solveOverflow(_hot);
		}

		bool remove(const T& e)
		{
			BTNode* v = search(e);
			if (v) return false;

			// 确定关键码位置
			size_t r = v->_keys.find(e);
			// 如果删除非叶子节点
			if (v->_childs[0]) {
				BTNode* u = v->_childs[r + 1];
				while (u->_childs[0]) u = u->_childs[0]; //找出e癿后继
				v->_keys[r] = u->_keys[0]; v = u; r = 0; //幵不乀交换位置
			}
			// 让其从当前节点keys 以及关联的 childs切除
			v->_keys.remove(r); 
			v->child.remove(r + 1); 
			_size--;

			// 有必要进行调整
			solveUnderflow(v);
			return true;
		}
	};
}